//
// Created by PC on 2017/12/20.
//

#ifndef VERTEXADJACENTITERATOR_SPARSEGRAPH_H
#define VERTEXADJACENTITERATOR_SPARSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/**
 * 稀疏图 邻接表
 */
class SparseGraph{
private:
    int n,m;
    bool directed;
    vector<vector<int>> g;
public:
    SparseGraph(int n, bool directed){
        this->n=n;
        this->m=0;
        this->directed=directed;
        g=vector<vector<int> >(n,vector<int>());
    }
    ~SparseGraph(){}
    int V(){ return n; }
    int E(){ return m; }

    void addEdge(int v, int w) {
        assert(v>=0&&v<n);
        assert(w>=0&&w<n);

        //排除自环边
        //排除平行边
        if(hasEdge(v,w)||v==w)
            return;
        g[v].push_back(w);
        if(!directed)
            g[w].push_back(v);
        m++;
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v][i] == w )
                return true;
        return false;
    }
    class adjIterator{
    private:
        int v;
        int index;
        SparseGraph &G;
    public:
        adjIterator(int v,SparseGraph &graph):G(graph){
            assert(v>=0&&v<G.n);
            this->v=v;
            this->index=0;
        }
        ~adjIterator(){}

        int begin(){
            index=0;
            if(G.g[v].size())
                return G.g[v][index];
            return -1;
        }

        int next(){
            index++;
            if(index<G.g[v].size())
                return G.g[v][index];
            return -1;
        }

        bool end(){
            return index>=G.g[v].size();
        }
    };

};
#endif //VERTEXADJACENTITERATOR_SPARSEGRAPH_H
